The term “ray tracing” describes a technique for synthesizing photorealistic images by identifying all light paths that connect light sources with cameras and summing up these contributions. The simulation traces rays along the line of sight to determine visibility, and traces rays from the light sources in order to determine illumination.
Ray tracing has become mainstream in motion pictures and other applications. However, current ray tracing techniques suffer from a number of known limitations and weaknesses, including numerical problems, limited capabilities to process dynamic scenes, slow setup of acceleration data structures, and large memory footprints. Thus, current ray tracing techniques lack the capability to deal efficiently with fully animated scenes, such as wind blowing through a forest or a person's hair. Overcoming the limitations of current ray tracing systems would also enable the rendering of, for example, higher quality motion blur in movie productions.
Current attempts to improve the performance of ray tracing systems have fallen short for a number of reasons. For example, current real-time ray tracing systems generally use 3D-trees as their acceleration structure, which are based on axis-aligned binary space partitions. Because the main focus of these systems is on rendering static scenes, they typically fail to address the significant amount of setup time required to construct the required data structures in connection with fully animated scenes. Along these lines, one manufacturer has improved real-time ray tracing by building efficient 3D-trees and developing a technique able to shorten the time needed to traverse the tree. However, it can be shown that the expected memory requirement for the system increases quadratically with an increase in the number of objects to be ray-traced.
Another manufacturer has designed a ray tracing integrated circuit that uses bounding volume hierarchies to improve system performance. However, it has been found that the architecture's performance breaks down if too many incoherent secondary rays are traced.
In addition, attempts have made to improve system performance by implementing 3D-tree traversal techniques using field-programmable gate arrays (FPGAs). The main increase in processing speed in these systems is obtained by tracing bundles of coherent rays and exploiting the capability of FPGAs to perform rapid hardwired computations.
The construction of acceleration structures has not yet been implemented in hardware. The FPGA implementations typically use floating point techniques at reduced precision.
A number of different techniques can be used to simulate photon trajectories, including Markov chains. The use of quasi-Monte Carlo techniques in simulating Markov chains is described, for example, in: L'Ecuyer et al., Randomized Quasi-Monte Carlo Simulation of Markov Chains with an Ordered State Space (2004) (“L'Ecuyer”), which is incorporated herein by reference as if set forth in its entirety.
L'Ecuyer discusses the use of a randomized quasi-Monte Carlo method for estimating the state distribution at each step of a Markov chain with totally ordered (discrete or continuous) state space. The number of steps in the chain can be random and unbounded. The method can be used in particular to get a low-variance unbiased estimator of the expected total cost up to some random stopping time, when state dependent costs are paid at each step. That paper provides numerical illustrations where the variance reduction with respect to standard Monte Carlo is substantial.
L'Ecuyer notes that a deterministic quasi-Monte Carlo method for estimating transient measures over a fixed number of steps, for discrete-time and discrete-state Markov chains with a totally ordered state space, was proposed and studied in the following papers, which are also incorporated herein by reference in their entireties:
Lécot et al., “Quasi-Random Walk Methods,” Monte Carlo and Quasi-Monte Carlo Methods 2000, pp. 63-85, Springer-Vertlag (Berlin, 2002).
Lécot et al., “Quasi-Monte Carlo Methods for Estimating Transient Measures of Discrete time Markov Chains,” Monte Carlo and Quasi-Monte Carlo and Quasi-Monte Carlo Methods 2002, pp. 329-42, Springer-Verlag (Berlin, 2004) (“Lécot 2004”).
L'Ecuyer describes a technique that simulates n=2k copies of the chain in parallel, for the same number of steps, using a (0, 2)-sequence in base 2. At step j of the chain, it reorders the n copies according to their states and simulates the transitions (i.e., next states) for the n copies by employing the elements nj to nj+n−1 of the (0, 2)-sequence in place of uniform random numbers to drive the simulation. It assumes that simulating each transition of the chain requires a single uniform random variate. Convergence to the correct value was proved in Lécot 2004 under a condition on the structure of the transition matrix of the Markov chain.
L'Ecuyer attempts to generalize the technique to Markov chains with continuous state space, with a random and unbounded number of steps (and it is claimed that such a technique permits one to cover regenerative simulation, in particular), and for which the number d of uniform random variates that are required to generate the next state in one step of the Markov chain can be larger than 1.
However, while various researchers have postulated the use of Markov chains to simulate photon trajectories and the like, previous techniques of using quasi-Monte Carlo methods to simulate Markov chains, e.g., trajectories of photons, provided only moderate improvements over random sampling. However, QMC methods in accordance with the present invention, as described below, can exploit the intrinsic low-dimensional structure of the solution operator, yielding much more efficient techniques.
Thus, prior to the present invention, there was still a need for more efficient methods, systems, apparatus, devices and software program/code products for simultaneously simulating Markov chains.
It would be desirable, therefore, to provide improved and more efficient methods, systems, apparatus, devices and software program/code products for simulating Markov chains, using Quasi-Monte Carlo techniques and sorting strategies.